<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<html>
<head>
<link rel="STYLESHEET" href="lib.css" type='text/css' />
<link rel="SHORTCUT ICON" href="../icons/pyfav.png" type="image/png" />
<link rel='start' href='../index.html' title='Python documentation Index' />
<link rel="first" href="lib.html" title='Python library Reference' />
<link rel='contents' href='contents.html' title="Contents" />
<link rel='index' href='genindex.html' title='Index' />
<link rel='last' href='about.html' title='About this document...' />
<link rel='help' href='about.html' title='About this document...' />
<link rel="next" href="defaultdict-objects.html" />
<link rel="prev" href="module-collections.html" />
<link rel="parent" href="module-collections.html" />
<link rel="next" href="deque-recipes.html" />
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<meta name='aesop' content='information' />
<title>5.3.1 deque objects </title>
</head>
<body>
<div class="navigation">
<div id='top-navigation-panel' xml:id='top-navigation-panel'>
<table align="center" width="100%" cellpadding="0" cellspacing="2">
<tr>
<td class='online-navigation'><a rel="prev" title="5.3 collections  "
  href="module-collections.html"><img src='../icons/previous.png'
  border='0' height='32'  alt='Previous Page' width='32' /></a></td>
<td class='online-navigation'><a rel="parent" title="5.3 collections  "
  href="module-collections.html"><img src='../icons/up.png'
  border='0' height='32'  alt='Up one Level' width='32' /></a></td>
<td class='online-navigation'><a rel="next" title="5.3.1.1 Recipes"
  href="deque-recipes.html"><img src='../icons/next.png'
  border='0' height='32'  alt='Next Page' width='32' /></a></td>
<td align="center" width="100%">Python Library Reference</td>
<td class='online-navigation'><a rel="contents" title="Table of Contents"
  href="contents.html"><img src='../icons/contents.png'
  border='0' height='32'  alt='Contents' width='32' /></a></td>
<td class='online-navigation'><a href="modindex.html" title="Module Index"><img src='../icons/modules.png'
  border='0' height='32'  alt='Module Index' width='32' /></a></td>
<td class='online-navigation'><a rel="index" title="Index"
  href="genindex.html"><img src='../icons/index.png'
  border='0' height='32'  alt='Index' width='32' /></a></td>
</tr></table>
<div class='online-navigation'>
<b class="navlabel">Previous:</b>
<a class="sectref" rel="prev" href="module-collections.html">5.3 collections  </a>
<b class="navlabel">Up:</b>
<a class="sectref" rel="parent" href="module-collections.html">5.3 collections  </a>
<b class="navlabel">Next:</b>
<a class="sectref" rel="next" href="deque-recipes.html">5.3.1.1 Recipes</a>
</div>
<hr /></div>
</div>
<!--End of Navigation Panel-->

<h2><a name="SECTION007310000000000000000"></a><a name="deque-objects"></a>
<br>
5.3.1 <tt class="class">deque</tt> objects 
</h2>

<p>
<dl><dt><table cellpadding="0" cellspacing="0"><tr valign="baseline">
  <td><nobr><b><tt id='l2h-733' xml:id='l2h-733' class="function">deque</tt></b>(</nobr></td>
  <td><var></var><big>[</big><var>iterable</var><big>]</big><var></var>)</td></tr></table></dt>
<dd>
  Returns a new deque object initialized left-to-right (using
  <tt class="method">append()</tt>) with data from <var>iterable</var>.  If <var>iterable</var>
  is not specified, the new deque is empty.

<p>
Deques are a generalization of stacks and queues (the name is pronounced
  ``deck'' and is short for ``double-ended queue'').  Deques support
  thread-safe, memory efficient appends and pops from either side of the deque
  with approximately the same <code>O(1)</code> performance in either direction.

<p>
Though <tt class="class">list</tt> objects support similar operations, they are optimized
  for fast fixed-length operations and incur <code>O(n)</code> memory movement costs
  for "<tt class="samp">pop(0)</tt>" and "<tt class="samp">insert(0, v)</tt>" operations which change both the
  size and position of the underlying data representation.
  
<span class="versionnote">New in version 2.4.</span>

</dl>

<p>
Deque objects support the following methods:

<p>
<dl><dt><table cellpadding="0" cellspacing="0"><tr valign="baseline">
  <td><nobr><b><tt id='l2h-734' xml:id='l2h-734' class="method">append</tt></b>(</nobr></td>
  <td><var>x</var>)</td></tr></table></dt>
<dd>
   Add <var>x</var> to the right side of the deque.
</dl>

<p>
<dl><dt><table cellpadding="0" cellspacing="0"><tr valign="baseline">
  <td><nobr><b><tt id='l2h-735' xml:id='l2h-735' class="method">appendleft</tt></b>(</nobr></td>
  <td><var>x</var>)</td></tr></table></dt>
<dd>
   Add <var>x</var> to the left side of the deque.
</dl>

<p>
<dl><dt><table cellpadding="0" cellspacing="0"><tr valign="baseline">
  <td><nobr><b><tt id='l2h-736' xml:id='l2h-736' class="method">clear</tt></b>(</nobr></td>
  <td><var></var>)</td></tr></table></dt>
<dd>
   Remove all elements from the deque leaving it with length 0.
</dl>

<p>
<dl><dt><table cellpadding="0" cellspacing="0"><tr valign="baseline">
  <td><nobr><b><tt id='l2h-737' xml:id='l2h-737' class="method">extend</tt></b>(</nobr></td>
  <td><var>iterable</var>)</td></tr></table></dt>
<dd>
   Extend the right side of the deque by appending elements from
   the iterable argument.
</dl>

<p>
<dl><dt><table cellpadding="0" cellspacing="0"><tr valign="baseline">
  <td><nobr><b><tt id='l2h-738' xml:id='l2h-738' class="method">extendleft</tt></b>(</nobr></td>
  <td><var>iterable</var>)</td></tr></table></dt>
<dd>
   Extend the left side of the deque by appending elements from
   <var>iterable</var>.  Note, the series of left appends results in
   reversing the order of elements in the iterable argument.
</dl>

<p>
<dl><dt><table cellpadding="0" cellspacing="0"><tr valign="baseline">
  <td><nobr><b><tt id='l2h-739' xml:id='l2h-739' class="method">pop</tt></b>(</nobr></td>
  <td><var></var>)</td></tr></table></dt>
<dd>
   Remove and return an element from the right side of the deque.
   If no elements are present, raises an <tt class="exception">IndexError</tt>.
</dl>

<p>
<dl><dt><table cellpadding="0" cellspacing="0"><tr valign="baseline">
  <td><nobr><b><tt id='l2h-740' xml:id='l2h-740' class="method">popleft</tt></b>(</nobr></td>
  <td><var></var>)</td></tr></table></dt>
<dd>
   Remove and return an element from the left side of the deque.
   If no elements are present, raises an <tt class="exception">IndexError</tt>.   
</dl>

<p>
<dl><dt><table cellpadding="0" cellspacing="0"><tr valign="baseline">
  <td><nobr><b><tt id='l2h-741' xml:id='l2h-741' class="method">remove</tt></b>(</nobr></td>
  <td><var>value</var>)</td></tr></table></dt>
<dd>
   Removed the first occurrence of <var>value</var>.  If not found,
   raises a <tt class="exception">ValueError</tt>.
   
<span class="versionnote">New in version 2.5.</span>

</dl>

<p>
<dl><dt><table cellpadding="0" cellspacing="0"><tr valign="baseline">
  <td><nobr><b><tt id='l2h-742' xml:id='l2h-742' class="method">rotate</tt></b>(</nobr></td>
  <td><var>n</var>)</td></tr></table></dt>
<dd>
   Rotate the deque <var>n</var> steps to the right.  If <var>n</var> is
   negative, rotate to the left.  Rotating one step to the right
   is equivalent to:  "<tt class="samp">d.appendleft(d.pop())</tt>". 
</dl>

<p>
In addition to the above, deques support iteration, pickling, "<tt class="samp">len(d)</tt>",
"<tt class="samp">reversed(d)</tt>", "<tt class="samp">copy.copy(d)</tt>", "<tt class="samp">copy.deepcopy(d)</tt>",
membership testing with the <tt class="keyword">in</tt> operator, and subscript references
such as "<tt class="samp">d[-1]</tt>".

<p>
Example:

<p>
<div class="verbatim"><pre>
&gt;&gt;&gt; from collections import deque
&gt;&gt;&gt; d = deque('ghi')                 # make a new deque with three items
&gt;&gt;&gt; for elem in d:                   # iterate over the deque's elements
...     print elem.upper()	
G
H
I

&gt;&gt;&gt; d.append('j')                    # add a new entry to the right side
&gt;&gt;&gt; d.appendleft('f')                # add a new entry to the left side
&gt;&gt;&gt; d                                # show the representation of the deque
deque(['f', 'g', 'h', 'i', 'j'])

&gt;&gt;&gt; d.pop()                          # return and remove the rightmost item
'j'
&gt;&gt;&gt; d.popleft()                      # return and remove the leftmost item
'f'
&gt;&gt;&gt; list(d)                          # list the contents of the deque
['g', 'h', 'i']
&gt;&gt;&gt; d[0]                             # peek at leftmost item
'g'
&gt;&gt;&gt; d[-1]                            # peek at rightmost item
'i'

&gt;&gt;&gt; list(reversed(d))                # list the contents of a deque in reverse
['i', 'h', 'g']
&gt;&gt;&gt; 'h' in d                         # search the deque
True
&gt;&gt;&gt; d.extend('jkl')                  # add multiple elements at once
&gt;&gt;&gt; d
deque(['g', 'h', 'i', 'j', 'k', 'l'])
&gt;&gt;&gt; d.rotate(1)                      # right rotation
&gt;&gt;&gt; d
deque(['l', 'g', 'h', 'i', 'j', 'k'])
&gt;&gt;&gt; d.rotate(-1)                     # left rotation
&gt;&gt;&gt; d
deque(['g', 'h', 'i', 'j', 'k', 'l'])

&gt;&gt;&gt; deque(reversed(d))               # make a new deque in reverse order
deque(['l', 'k', 'j', 'i', 'h', 'g'])
&gt;&gt;&gt; d.clear()                        # empty the deque
&gt;&gt;&gt; d.pop()                          # cannot pop from an empty deque
Traceback (most recent call last):
  File "&lt;pyshell#6&gt;", line 1, in -toplevel-
    d.pop()
IndexError: pop from an empty deque

&gt;&gt;&gt; d.extendleft('abc')              # extendleft() reverses the input order
&gt;&gt;&gt; d
deque(['c', 'b', 'a'])
</pre></div>

<p>

<p><br /></p><hr class='online-navigation' />
<div class='online-navigation'>
<!--Table of Child-Links-->
<a name="CHILD_LINKS"><strong>Subsections</strong></a>

<ul class="ChildLinks">
<li><a href="deque-recipes.html">5.3.1.1 Recipes</a>
</ul>
<!--End of Table of Child-Links-->
</div>

<div class="navigation">
<div class='online-navigation'>
<p></p><hr />
<table align="center" width="100%" cellpadding="0" cellspacing="2">
<tr>
<td class='online-navigation'><a rel="prev" title="5.3 collections  "
  href="module-collections.html"><img src='../icons/previous.png'
  border='0' height='32'  alt='Previous Page' width='32' /></a></td>
<td class='online-navigation'><a rel="parent" title="5.3 collections  "
  href="module-collections.html"><img src='../icons/up.png'
  border='0' height='32'  alt='Up one Level' width='32' /></a></td>
<td class='online-navigation'><a rel="next" title="5.3.1.1 Recipes"
  href="deque-recipes.html"><img src='../icons/next.png'
  border='0' height='32'  alt='Next Page' width='32' /></a></td>
<td align="center" width="100%">Python Library Reference</td>
<td class='online-navigation'><a rel="contents" title="Table of Contents"
  href="contents.html"><img src='../icons/contents.png'
  border='0' height='32'  alt='Contents' width='32' /></a></td>
<td class='online-navigation'><a href="modindex.html" title="Module Index"><img src='../icons/modules.png'
  border='0' height='32'  alt='Module Index' width='32' /></a></td>
<td class='online-navigation'><a rel="index" title="Index"
  href="genindex.html"><img src='../icons/index.png'
  border='0' height='32'  alt='Index' width='32' /></a></td>
</tr></table>
<div class='online-navigation'>
<b class="navlabel">Previous:</b>
<a class="sectref" rel="prev" href="module-collections.html">5.3 collections  </a>
<b class="navlabel">Up:</b>
<a class="sectref" rel="parent" href="module-collections.html">5.3 collections  </a>
<b class="navlabel">Next:</b>
<a class="sectref" rel="next" href="deque-recipes.html">5.3.1.1 Recipes</a>
</div>
</div>
<hr />
<span class="release-info">Release 2.5.1, documentation updated on 18th April, 2007.</span>
</div>
<!--End of Navigation Panel-->
<address>
See <i><a href="about.html">About this document...</a></i> for information on suggesting changes.
</address>
</body>
</html>
